A microprocessor is a general-purpose computing architecture, also known as a central processing unit (CPU). The microprocessor includes an arithmetic logic unit (ALU), an accumulator, a plurality of registers, a program counter, a stack pointer, a clock circuit, and a plurality of interrupt circuits. In building a complete computing system, the microprocessor must be supplemented with external components, such as a random-access memory (RAM) and a read-only memory (ROM), an oscillator, a plurality of memory decoders, a plurality of Input/Output (I/O) interfaces (ports), and a plurality of other devices, such as video displays and disk drives. The microprocessor is designed to perform a wide variety of calculations with data and return the results to a user or another machine. The microprocessor achieves this computing power through the use of a sophisticated instruction set that may contain a plurality of instructions for performing arithmetic operations, bit movement operations, memory fetch and store operations, etc. Because of the complexity of the calculations that the microprocessor performs, the programs that control its operation are generally relatively large, requiring the use of mass storage devices to house them. When needed for a specific calculation or task, a program is loaded into the system RAM and executed by the microprocessor.
The primary design factors related to the microprocessor are flexibility and expandability, allowing the microprocessor to handle almost any task. This adaptability has resulted in a relatively large demand for the microprocessor and has enabled manufacturers to mass-produce them, resulting in a relatively inexpensive and disposable product.
Like the microprocessor, a microcontroller is also a general-purpose computing architecture. The microcontroller differs from the microprocessor, however, in that it can operate as a complete, stand-alone computer system. The microcontroller includes all of the components of the microprocessor, in addition to its own RAM, ROM, plurality of counters, and I/O ports. The microcontroller is also relatively flexible and can be used in a plurality of applications, however, the microcontroller is intended for use in a relatively static environment, requiring its programs to change minimally over time. The microcontroller is primarily intended to be used to control the environment within which it operates. The microcontroller is typically used in embedded system applications for monitoring and automation purposes. The microcontroller can be found in, for example, appliances (such as microwave ovens, refrigerators, televisions, VCRs, and stereos), automobiles (such as in engine control systems, diagnostics systems, and climate control systems), environmental control systems (such as in factories, greenhouses, and homes), instrumentation arrays, and aerospace systems.
The microprocessor differs from the microcontroller in their sets of operational codes. The microprocessor has far more operational codes for moving data to and from an external memory than the microcontroller, which may only have a few such operational codes. From an internal bit-handling perspective, the microcontroller has far more internal bit-handling operational codes than the microprocessor, which may only have a few. The architecture of both the microprocessor and the microcontroller are intended for mass use and are designed for flexibility and expandability. Each has the goal of supporting a wide range of applications. While the primary use of the microprocessor is for calculation-intensive computing, the microcontroller is designed to handle smaller calculations and to control its environment.
The short-circuit evaluation of a Boolean expression or operation is simply the abandonment of the remainder of the expression or operation once its value has been determined. If the outcome of the expression or operation can be determined prior to its full evaluation, it makes sense to save processing cycles by avoiding the remaining, unnecessary, conditional tests of the expression or operation. In other words, the short-circuit evaluation of a Boolean expression is a technique that specifies the partial evaluation of the expression involving an AND and an OR operation.
What is needed is a microprocessor and/or a microcontroller that is capable of evaluating complex Boolean expressions that are in Conjunctive Normal Form (CNF). Disjunctive Normal Form (DNF) Boolean expressions can also be incorporated into the architecture of the microprocessor and/or the microcontroller, however, there are inefficiencies associated with the processing of the DNF equivalents of CNF expressions.
A Boolean expression is in DNF if it is expressed as the sum (OR) of products (AND). That is, the Boolean expression B is in DNF if it is written as:A1 OR A2 OR A3 OR . . . An,where each term Ai is expressed as:T1 AND T2 AND . . . AND Tm,where each term Ti is either a simple variable, or the negation (NOT) of a simple variable. Each term Ai is referred to as a “minterm”. A Boolean expression is in CNF if it is expressed as the product (AND) of sums (OR). That is, the Boolean expression B is in CNF if it is written as:O1 AND O2 AND O3 AND . . . On,where each term Oi is expressed as:T1 OR T2 OR . . . OR Tm,where each term Ti is either a simple variable, or the negation (NOT) of a simple variable. Each term Oi is referred to as a “maxterm”. The terms “minterm” and “maxterm” can also be referred to as “disjunct” and “conjunct”, respectively.
The short-circuit evaluations of a CNF Boolean expression and a DNF Boolean expression are handled differently. In the case of a CNF expression, short-circuiting can occur if any of the conjuncts evaluates to false. In the following example,(AB)(CD),if either of the conjuncts, (AB) or (CD), evaluates to false, the expression also evaluates to false. If (AB) evaluates to false, the remainder of the expression can be eliminated, thereby saving the time required to evaluate the other conjunct. In contrast to CNF short-circuit evaluation, a DNF expression can be short-circuited if any of the disjuncts evaluates to true. Using the previous example in DNF,(AC)(AD)(BC)(BD),if any of the disjuncts, (AC), (AD), (BC), or (BD), evaluates to true, the expression also evaluates to true. For example, if (AC) evaluates to true, the evaluation of the remaining three disjuncts can be eliminated, since their values are irrelevant to the outcome of the expression.
Thus, the short-circuit evaluation of both CNF and DNF expressions becomes increasingly valuable, in terms of cycle savings, as the complexity of the expressions increases. In large scale monitoring and automation applications, the short-circuit evaluation of both CNF and DNF expressions is essential.